package Z.dailyExercise._0221slidingWindow;

import java.util.*;

/**
 *
 */
public class _1438_绝对差不超过限制的最长连续子数组 {
    /**
     * 滑窗方法：多写一个函数专门用于计算数组的最大绝对差
     * ==超时， 其中判断最大绝对差的函数可以采用treemap来实现 但还是很慢
     * @param nums
     * @param limit
     * @return
     */
    public int longestSubarray(int[] nums, int limit) {
        int i=0,j=1;
        int maxRes = Integer.MIN_VALUE;
        while (j<nums.length){
            int[] temp = Arrays.copyOfRange(nums,i,j);
            int res = helper(temp);
            if (res<=limit){
                //后指针后移动一位
                j++;
                maxRes = Math.max(temp.length,maxRes);
            }else {
                i++;
            }

        }
        return maxRes;

    }

    public int helper(int[] nums){
        Arrays.sort(nums);
        return nums[nums.length-1]-nums[0];
    }

    public static void main(String[] args) {
        _1438_绝对差不超过限制的最长连续子数组  Test = new _1438_绝对差不超过限制的最长连续子数组();
        System.out.println(Test.longestSubarray1(new int[]{8,4,3,7},4));

    }

    /**
     * 加速思路；重要的就是求极值 所以建立两个最值栈进行存储
     * --有问题 在栈里被pop走了最大值之后 栈里没有一个递减的数列进行下一次判断是不是小雨limit
     * --所以还是采用 单调队列的方法 双端队列 来的数如果大于最大对垒的last 那么就一直弹出 队首是最大值
     * @param nums
     * @param limit
     * @return
     */
    public int longestSubarray1(int[] nums, int limit) {
        Stack<Integer> maxstack = new Stack<>();
        Stack<Integer> minstack = new Stack<>();
//        maxstack.push(nums[0]);
//        minstack.push(nums[0]);
        int i=0,j=0,res=0;
        while (j<nums.length){
            if (maxstack.isEmpty() || nums[j]>maxstack.peek()  ){
                maxstack.push(nums[j]);
            }
            if (minstack.isEmpty()  || nums[j]<minstack.peek() ){
                minstack.push(nums[j]);
            }
            j++;
            while (maxstack.peek()-minstack.peek() > limit){

                 if (maxstack.peek()== nums[i]){
                     maxstack.pop();

                 }
                if (minstack.peek()== nums[i]){
                    minstack.pop();
                }
                i++;

            }
            res = Math.max(res,j-i+1);
        }

        return res;






    }

    public int longestSubarray_Deque(int[] nums, int limit) {
        Deque<Integer> maxQueue = new ArrayDeque<>();
        Deque<Integer> minQueue = new ArrayDeque<>();
        int l = 0, r = 0, res = 0;
        while (r < nums.length) {
            while (!maxQueue.isEmpty() && nums[r] > maxQueue.peekLast())
                maxQueue.removeLast();
            while (!minQueue.isEmpty() && nums[r] < minQueue.peekLast())
                minQueue.removeLast();
            maxQueue.add(nums[r]);
            minQueue.add(nums[r]);
            r++;
            while (maxQueue.peek() - minQueue.peek() > limit) {
                if (maxQueue.peek() == nums[l]) maxQueue.remove();
                if (minQueue.peek() == nums[l]) minQueue.remove();
                l += 1;
            }
            res = Math.max(res, r - l);
        }
        return res;
    }


}
